// // https://www.lintcode.com/problem/sliding-window-median/description
// // 总体时间复杂度 O(nlogk)O(nlogk)，n是元素个数，k 是 window 的大小。 (为什么要两个乘？
// // priority_queue不支持删除，multiset支持

// class Solution {
// public:
//     /**
//      * @param nums: A list of integers
//      * @param k: An integer
//      * @return: The median of the element inside the window at each moving
//      */
//     vector<int> medianSlidingWindow(vector<int> &nums, int k) {
//         multiset<int> minHeap, maxHeap;
//         vector<int> res;
//         for (int i = 0; i < nums.size(); ++i) {
//             if (maxHeap.empty() || nums[i] <= *maxHeap.rbegin()) //end没有元素，rbegin有
//             {
//                 maxHeap.insert(nums[i]);
//             } else {
//                 minHeap.insert(nums[i]);
//             }
//             cout << maxHeap.size() << endl;
//             cout << minHeap.size() << endl;
//             while (maxHeap.size() != minHeap.size() && maxHeap.size() - 1 != minHeap.size()) {
//                 if (maxHeap.size() > minHeap.size()) {
//                     int top = *maxHeap.rbegin();
//                     maxHeap.erase(maxHeap.lower_bound(*maxHeap.rbegin())); 
//                     // maxHeap.erase(maxHeap.rbegin()); //但是不能传reverse_iterator
//                     minHeap.insert(top);
//                 } else {
//                     int top = *minHeap.begin();
//                     // minHeap.erase(minHeap.lower_bound(*minHeap.begin()));
//                     // minHeap.erase(0); 错的 这个传的是值而不是iterator
//                     minHeap.erase(minHeap.begin());
//                     maxHeap.insert(top);
//                 }
//             }
//             // if (maxHeap.size() == (k - 1) / 2 && ) {
//             if (maxHeap.size() + minHeap.size() == k) {
                
//                 res.push_back(*maxHeap.rbegin());
//                 int idx = i - k + 1;
//                 if (maxHeap.find(nums[idx]) != maxHeap.end()) {
//                     maxHeap.erase(maxHeap.find(nums[idx]));
//                 } else {
//                     minHeap.erase(maxHeap.find(nums[idx])); //注意erase的是位置
//                 }
//             }
//         }
//         return res;
//     }
// };

// // iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。
// // iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值> key的第一个元素。
// // 函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元
// // 小于val，则返回last的位置
// // https://blog.csdn.net/hpu_zyh/article/details/11497527
// // lower_bound(a,a+n,key) 


// 一开始就调整好堆大小，然后删掉哪个里面的就加到那个里面就行了。
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of the element inside the window at each moving
     */
    vector<int> medianSlidingWindow(vector<int> &nums, int k) {
        // write your code here
        vector<int> result;
        int n = nums.size();
        if (n == 0)
            return result;

        multiset<int> max, min;
        for (int i = 0; i < k; ++i) {
            max.insert(nums[i]);
        }
        // for (int i = 0; i < k / 2; ++k) { !!!
         for (int i = 0; i < k / 2; ++i) {
            min.insert(*max.rbegin());
            max.erase(max.lower_bound(*max.rbegin()));
        }
        for (int i = k; i < n; ++i) {
            result.push_back(*max.rbegin());
            if (max.find(nums[i - k]) != max.end()) {
                max.erase(max.find(nums[i - k]));
                max.insert(nums[i]);
            } else {
                min.erase(min.find(nums[i - k]));
                min.insert(nums[i]);
            }
            if (!min.empty() && !max.empty() && *min.begin() < *max.rbegin()) {
                // max.insert(*min.begin());
                // min.erase(min.begin());
                // min.insert(*max.rbegin());
                // max.erase(max.upper_bound(*max.rbegin()));
                
                int tmp = *max.rbegin();
                max.erase(max.lower_bound(*max.rbegin()));
                max.insert(*min.begin());
                min.erase(min.begin());
                min.insert(tmp); //不管需不需要，这样做保险
            }
        }
        result.push_back(*max.rbegin());
        return result;
    }
};

// todo:写个堆来做logn删除